package binary_tree.leetcode.medium;

/**
 * @author bruin_du
 * @description 树的子结构
 * @date 2022/5/21 23:30
 **/
public class Offer26_IsSubStructure {
    boolean flag = false;// 剪枝
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (flag || (A == null && B == null)) return true;
        if (A == null || B == null) return false;
        if (A.val == B.val && compare(A, B)) {
            flag = true;
            return true;
        }
        return isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    boolean compare(TreeNode A, TreeNode B) {
        if (B == null) return true;
        if (A == null || A.val != B.val) return false;
        return compare(A.left, B.left) && compare(A.right, B.right);
    }
}
